/**
 * 
 */
package leetCode;

import java.util.PriorityQueue;

/**
 * @author zhong
 *
 */
public class NetworkDelayTime {
	public int networkDelayTime(int[][] times, int N, int K) {
		int[] time = new int[N];
		for (int i = 0; i < N; i++) {
			time[i] = Integer.MAX_VALUE;
		}
		times = preProcess(times, N);
		if (times == null) {
			return -1;
		}
		K--;
		PriorityQueue<Integer> queue = new PriorityQueue<>(N, (a, b) -> (time[a] - time[b]));
		queue.offer(K);
		boolean[] visited = new boolean[N];
		time[K] = 0;
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			visited[cur] = true;
			System.out.println(cur + " " + time[cur]);
			for (int i = 0; i < N; i++) {
				if (!visited[i]) {// 没有固定的节点
					if (times[cur][i] != -1 && time[i] > time[cur] + times[cur][i]) {// 更新时间
						time[i] = time[cur] + times[cur][i];
						queue.offer(i);
					}
				}
			}
		}
		int max = 0;
		for (int c : time) {
			if (c == Integer.MAX_VALUE) {
				return -1;
			}
			max = Math.max(max, c);
		}
		return max;
	}

	public int networkDelayTime2(int[][] times, int N, int K) {
		int[] time = new int[N];
		for (int i = 0; i < N; i++) {
			time[i] = Integer.MAX_VALUE;
		}
		times = preProcess(times, N);
		if (times == null) {
			return -1;
		}
		boolean[] visited = new boolean[N];
		int start = K - 1;
		time[start] = 0;
		int j = 1;
		while (j < N) {
			visited[start] = true;
			int minIndex = -1;
			for (int i = 0; i < N; i++) {
				if (!visited[i]) {
					if (times[start][i] != -1) {// 如果这条边可达
						time[i] = Math.min(time[start] + times[start][i], time[i]);
					}
					if (time[i] != Integer.MAX_VALUE && (minIndex == -1 || time[minIndex] > time[i])) {
						minIndex = i;
					}
				}
			}
			if (minIndex == -1) {// 不能到达所有点
				return -1;
			}
			start = minIndex;
			j++;
		}
		return time[start];
	}

	private int[][] preProcess(int[][] times, int N) {
		int[][] res = new int[N][N];
		for (int i = 0; i < res.length; i++) {
			for (int j = 0; j < res.length; j++) {
				res[i][j] = -1;
			}
		}
		for (int[] is : times) {
			int i = is[0] - 1;
			int j = is[1] - 1;
			if (i >= N || j >= N) {
				return null;
			}
			res[i][j] = is[2];
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] times = { { 1, 2, 1 } };
		int K = 2;
		int N = 2;
		System.out.println(new NetworkDelayTime().networkDelayTime(times, N, K));
	}

}
